#include<bits/stdc++.h>
using namespace std;

class MedianFinder {
public:
    priority_queue<double, vector<double>, less<double>> max_q; 
    priority_queue<double, vector<double>, greater<double>> min_q; 
    MedianFinder() {

    }
    
    void addNum(int num) {
        if(max_q.empty()){
            max_q.push(num);
            return;
        }
        if(min_q.size() == max_q.size()){
            if(num >= max_q.top()){
                min_q.push(num);
                max_q.push(min_q.top());
                min_q.pop();
            }
            else max_q.push(num); 
        } 
        else{
            if(num >= max_q.top()){
                min_q.push(num);
            }
            else{
                max_q.push(num);
                min_q.push(max_q.top());
                max_q.pop();
            }
        }
    }
    
    double findMedian() {
        if(max_q.size() == min_q.size())return (max_q.top() + min_q.top()) / 2;
        return max_q.top();
    }
};

/**
 * 2021.8.27
 * 优先队列解法
 * 用两个优先队列，一个大顶堆存所有数字的前半部分（向上取整）
 * 一个小顶堆存所有数字的后半部分
 * 这样大顶堆的堆顶就是中位数（共奇数个数）或者两个堆顶数字的平均数就是中位数（共偶数个数）
 * 插入的时候注意维持这个特性即可。
 */